/*
463. Island Perimeter
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

*/

/*
总外边数=总块数*4-相邻块数*2
*/
class Solution
{
public:
    int islandPerimeter(vector<vector<int>> &grid)
    {
        if(grid.size() == 0 || grid[0].size() == 0) return 0;
        int n = grid.size();
        int m = grid[0].size();
        int sum = 0;
        int v = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j]) {
                    sum++;
                    v += j > 0 ? grid[i][j - 1] : 0;
                    v += i > 0 ? grid[i - 1][j] : 0;
                }
            }
        }
        return sum * 4 - v * 2;
    }
};

/*
先处理最上边一列
再处理最左边
左边迭代处理很慢,所以这个答案很慢
*/
class Solution
{
public:
    int islandPerimeter(vector<vector<int>> &grid)
    {
        if(grid.size() == 0 || grid[0].size() == 0) return 0;
        int n = grid.size();
        int m = grid[0].size();
        int sum = 0;
        int v = 0;
        int pre = 0;
        for(int i : grid[0]) {
            if(i) {
                sum++;
                v += pre;
            }
            pre = i;
        }
        pre = grid[0][0];
        for(int i = 1; i < n; i++) {
            if(grid[i][0]) {
                sum++;
                v += pre;
                pre = 1;
            } else {
                pre = 0;
            }
        }
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(grid[i][j]) {
                    sum++;
                    v += grid[i][j - 1] + grid[i - 1][j];
                }
            }
        }
        return sum * 4 - v * 2;
    }
};


class Solution
{
public:
    int islandPerimeter(vector<vector<int>> &grid)
    {
        if(grid.size() == 0 || grid[0].size() == 0) return 0;
        int n = grid.size();
        int m = grid[0].size();
        int sum = 0;
        int preup[m];
        int pre = 0;
        int k = 0;
        for(int i : grid[0]) {
            if(i) {
                sum += 4 - pre;
                preup[k++] = pre = 2;
            } else {
                preup[k++] = pre = 0;
            }
        }

        for(int i = 1; i < n; i++) {
            pre = 0;
            k = 0;
            for(int j : grid[i]) {
                if(j) {
                    sum += 4 - pre - preup[k];
                    preup[k++] = pre = 2;
                } else {
                    preup[k++] = pre = 0;
                }
            }
        }
        return sum;
    }
};
